#include "info/icut.h"
#include "util/util.h"
#include "base/cktname.h"
#include "rewrite/synit.h"
#include <limits.h>


static const char * cmder = "TREEMAP > " ;

///////////////////////////////////////////////////////////////////////////////
//                 CONST AND STATIC MEMBER/FUNCTION                          //
///////////////////////////////////////////////////////////////////////////////

static const unsigned short pifun[4] = {0xAAAA,0xCCCC,0xF0F0,0xFF00};
static const unsigned short mask[5]  = {1,3,0xF,0xFF,0xFFFF};

inline unsigned short expand( unsigned short f , unsigned i , unsigned j )
{
   return (i==j)?f:expand( (f<<(1<<i)) | f , i+1 , j );
}
static string tostr( unsigned i )
{
   char buf[13];
   sprintf( buf , "%d" , i );
   return string( buf );
}
static unsigned diff( unsigned d )
{
   unsigned h = 0;
   while( d ) h +=1 , d = d>>2;
   return h;
}
static unsigned short sim( InfoCut & info , unsigned short * fun  , unsigned x , unsigned * cut , unsigned size )
{
   vec<unsigned> cone;

   for( unsigned i = 0 ; i < size ; ++ i ) info._mrk[ cut[i] ] = true; 
   if( info._mrk[x] == false ){ cone.push( x ); info._mrk[x] = true; }

   unsigned t =x;
   unsigned ptr=0;

   while( ptr != cone.sz )
   {
      unsigned n = cone[ ptr ++ ];
      for( int i = 0 ; i < 2 ; ++i )
      {
         x = var(info[n].fanin[i]);
         if( info._mrk[x] == false ){ cone.push( x ); info._mrk[x] = true; }
      }
   }
   for( unsigned i = 0 ; i < cone.sz ; ++i ) info._mrk[ cone[i] ] = false;
   for( unsigned i = 0 ; i <  size ; ++ i ) info._mrk[ cut[i] ] = false; 

   std::sort( cone.data , cone.data+cone.sz );

   for( unsigned i = 0 ; i <  size ; ++ i ) fun[ cut[i] ] = pifun[i];
   for( unsigned i = 0 ; i < cone.sz ; ++ i)
   {
      AigNode n = info[ cone[i] ];
      fun[ cone[i] ] = (fun[ var(n.fanin[0]) ]^(-sign(n.fanin[0]))) &
                       (fun[ var(n.fanin[1]) ]^(-sign(n.fanin[1]))) ;
   }
   return fun[ t ]&mask[size];
}
///////////////////////////////////////////////////////////////////////////////
//                 CLASS DECLARATION                                         //
///////////////////////////////////////////////////////////////////////////////
static const unsigned dup_num[7] = {0,32,16,8,4,2,1};
struct LutTree
{
   static const unsigned HEIGHT     = 6;  // tree heigh 
   static const unsigned N_LEAFS    =  1<<((HEIGHT-1)<<1) ; //4^(HEIGHT-1);
   static const unsigned N_NODES    = ((1<<((HEIGHT)<<1))-1)/ 3 ;
   static const unsigned N_PARS     = ((1<<((HEIGHT-1)<<1))-1)/3 ;

   struct LutLeaf
   {
      unsigned in[4]; // index of the circuit 
      LutLeaf(){ in[0]=in[1]=in[2]=in[3]=0;}
      unsigned & operator[](unsigned i ){return in[i];}
      unsigned operator[]( unsigned i ) const {return in[i];}
   };

   //--- member data
   unsigned short  _dat [ N_NODES ];
   LutLeaf         _leaf[ N_LEAFS ]; 
   unsigned        _piidx;
   unsigned        _head;

   //--- constructor
   LutTree():_head(0){ memset( _dat , 0 , sizeof(unsigned short)*N_NODES ) ;}

   unsigned short & operator[]( unsigned i ){return _dat[i];}
   unsigned short operator[]( unsigned i )const{return _dat[i];}
   
   void write_bench( const char * file , CktName & n );
   void assign_leaf();
   void write_leaf( const char * file );
   void read_leaf( const char * file );
};
struct LutCkt // tmporary datastructure 
{
  struct Lut
  {
      unsigned short fun;
      unsigned short sz;
      unsigned short in[4];
      Lut( unsigned short f , unsigned s ):fun(f),sz(s){}
      Lut(){}
      unsigned short & operator[]( unsigned i ){ return in[i];}
      unsigned short operator[]( unsigned i )const{return in[i];}
  };

  Lut   *       luts;
  string *      names;

  unsigned      size;
  unsigned      pi;
  unsigned      po;

  LutCkt( unsigned i , unsigned s )
     :size(s+i),pi(i)
  { luts = new Lut[s+i]; names = new string[s+i]; }
  ~LutCkt(){delete [] luts;delete [] names; }
  
  Lut & operator[](unsigned i ){return luts[i];}
  const Lut & operator[](unsigned i )const{return luts[i];}
  
  void assignName( const CktName * n = NULL );
  void write_bench( const char * str );
};
struct MinCut // for DP mapping tracing record 
{
   MinCut( unsigned c , unsigned cn , unsigned ci ):cost(c),cutnum(cn),cutidx(ci){}
   MinCut():cost(0){}
   unsigned cost:8;
   unsigned cutnum:8;
   unsigned cutidx:16;
};
struct Bucket : public vec<unsigned> 
{
   void push( unsigned x , unsigned n )
   { 
      for( unsigned i = 0 ; i < n ; ++ i ) 
         vec<unsigned>::push( x ); 
   }
   void addSeq( unsigned i , unsigned j ){ while( i!= j )vec<unsigned>::push( i ++ ); }
   unsigned select(){ return data[ rand()%sz ] ; }
};
struct Fit // for DP remapping 
{
   unsigned idx;
   unsigned cut[4];
   Fit();
   Fit( unsigned i ):idx(i){}
};
//___ DPmappging ______________________________________________________________
//      
//  input: info , output a dynamic programming mapping result but not tracing
//  TODO balancing improvement
//  
//=============================================================================
static void DPmapping( const InfoCut & info , MinCut * m )
{
   // DP programming 
   for( unsigned i = info._andFlag ; i < info.size() ; ++i )
   {
      unsigned mincost = INT_MAX;
      for( int j = 3 ; j > 0 ; -- j )
      {
         const CutSet & c = info._cut[i][j];
         for( int k = 0 ; k < c.size ; ++ k )
         {
            unsigned maxlvl = m[ c[k][0] ].cost;
            for( int x = 1 ; x <= j ; ++x )
               if( maxlvl < m[ c[k][x] ].cost )
                  maxlvl = m[ c[k][x] ].cost;
            maxlvl += 1;
            if( maxlvl < mincost )
            { 
               mincost = maxlvl;
               m[i] = MinCut( mincost , j , k );
            }
         }
      }
      assert( mincost != INT_MAX );
   }
}
//___ Traversing the DP result ________________________________________________
//
//  Given a dp mapping, producing a traverse
//
//=============================================================================
static void traversing( const InfoCut & info , const MinCut * m , vec<unsigned short> & tv )
{
   int size    = info.size();
   int andFlag = info._andFlag;
   unsigned short focnt[size];

   memset( focnt , 0 , sizeof( unsigned short )*size );
   for( int i = 0 ; i < andFlag; ++i ) focnt[i] = 1;

   unsigned n = size-1;
   if( m[n].cost != 0 ) tv.push( n );
   else return;
   
   unsigned ptr = 0; 
   do
   {
      n = tv[ptr++];
      MinCut x = m[ n ];
      Cut    k = info._cut[ n ][ x.cutnum ][ x.cutidx ];
      for( unsigned i = 0 ; i <= x.cutnum ; ++ i )
      {
         if( focnt[ k[i] ] == 0 )
            tv.push( k[i] );
         focnt[ k[i] ]+=1;
      }
   }while( ptr != tv.sz );
   tv.clear();

   ptr = 0;
   tv.push( size-1 );
   do
   {
      n = tv[ ptr ++ ];
      MinCut x = m[ n ];
      Cut    k = info._cut[ n ][ x.cutnum ][ x.cutidx ];
      for( unsigned i = 0 ; i <= x.cutnum ; ++i )
         focnt[ k[i] ] -=1;;
      for( unsigned i = 0 ; i <= x.cutnum ; ++ i )
         if( focnt[k[i]] == 0 )
            tv.push( k[i] );
      
   }while( ptr != tv.sz );
}
//___ Factoring ________________________________________________________________
//
//  Given the dp mapping , cut information 
//  and back-traversing result 
//
//  producing the LutCkt
//
//=============================================================================
static void factor( InfoCut & info , const MinCut * m , const vec<unsigned short> & tv , LutCkt & ckt )
{
   int size    = info.size();
   int andFlag = info._andFlag;
   unsigned short cktidx[size];
   unsigned short cktfun[size];

   for( int i = 0 ; i < andFlag ; ++i )cktidx[i] = i;

   for( int i = tv.sz-1 , j= andFlag ; i >=0 ; -- i , ++j )
   {
      unsigned n = tv[i];
      MinCut x = m[ n ]; 
      Cut    k = info._cut[n][ x.cutnum ][x.cutidx ];
      unsigned fun = sim( info , cktfun , n , k.node , x.cutnum+1 );

      ckt[j] = LutCkt::Lut( fun , x.cutnum+1 );
      cktidx[ n ] = j ;
      for( unsigned z = 0 ; z <= x.cutnum ; ++z ) 
         ckt[j].in[z] = cktidx[ k[z] ];
   }
   ckt.po = cktidx[ var( info._po[0] ) ];
   if( sign( info._po[0] ) ) 
   {
      LutCkt::Lut & l = ckt[ ckt.po ];
      l.fun = mask[ l.sz ]&(~l.fun);
   }
//   ckt.assignName( tmpname );//   ckt.write_bench( "tmp.bench" );
}
//___ Expansion the LutCkt to the LutTree _____________________________________
//
//
//=============================================================================
static void duplication( const LutCkt & ckt , LutTree & t )
{
   unsigned mapping[ LutTree::N_NODES ] = {};
   unsigned pi = ckt.pi;
   t._piidx = pi ;

   mapping[0] = ckt.po;
   for( unsigned i = 0 ; i < LutTree::N_NODES; ++i ) 
   {
      unsigned n = mapping[i];
      if( n < pi ) continue;

      const LutCkt::Lut & k = ckt[n];
      t[i] = expand( k.fun , k.sz , 4 );

      for( int j = 0 ; j < k.sz ; ++ j )
         if( i < LutTree::N_PARS )
            mapping[ i*4 + j + 1 ] = k[j];
         else 
            t._leaf[ i - LutTree::N_PARS ].in[j] = k[j];
   }
   for( unsigned i = 0 ; i < LutTree::N_NODES ; ++i )
   {
      if( mapping[i] < pi && mapping[i] != 0)
      {
         t[i] = 0xAAAA;
         if( i < LutTree::N_PARS )
            mapping[ 4*i + 1 ] = mapping[i];
         else 
            t._leaf[ i - LutTree::N_PARS ].in[0] = mapping[i];
      }
   }
}
//____ TreeMap ________________________________________________________________
//
//  Dynamic programming
//  traversing
//  producing LutCkt
//  duplicate to LutTree
//
//=============================================================================
static bool treemap( InfoCut & info , LutTree & t )
{
   int size    = info.size();
   int andFlag = info._andFlag;
   
   MinCut m[size];
   DPmapping( info , m );
   cout << cmder << "the mapping Lut level is [ "<< m[size-1].cost <<" ]"<< endl;
   if( m[size-1].cost > 6 ){  return false;}

   vec<unsigned short> tv;
   traversing( info , m , tv );

   LutCkt ckt( andFlag , tv.sz );
   factor( info , m , tv , ckt );
   duplication( ckt , t );
   t.assign_leaf();

   return true;
}
//____ ReTreeMap ______________________________________________________________
//
//  Recursive Call 
//  : the complexity is the cut square 
//
//=============================================================================
static unsigned short * tmpfun;
static bool remap( InfoCut & info , LutTree & t , unsigned x , unsigned y );
static bool cutmap( InfoCut & info , LutTree & t , const unsigned * x , unsigned nx , unsigned * y , unsigned ny );
static bool re_treemap( InfoCut & ckt , LutTree & t )
{
   tmpfun = new unsigned short [ ckt.size() ];
   tmpfun[0] = 0xFFFF;
   
   bool res = remap( ckt , t , ckt.size()-1 , 0 );
   if( sign(ckt._po[0] ) )t[0] = ~t[0];
   delete [] tmpfun;

   return res;
}
///////////////////////////////////////////////////////////////////////////////
//                    STATIC FUNCTION FOR ReMAP                              //
///////////////////////////////////////////////////////////////////////////////
static bool isleaf( const Cut & c , int s, unsigned f )
{
   for( int i = 0 ; i < s ; ++ i) 
     if( c[i] >= f )return false;
   return true;
}
static bool find( const vec<Fit> & f , unsigned idx )
{
   for( unsigned i = 0 ; i < f.size() ; ++ i ) 
      if( f[i].idx == idx ) return true;
   return false;
}
static Fit & findfit( vec<Fit> & f , unsigned idx )
{
   for( unsigned i = 0 ; i < f.size() ; ++ i ) 
      if( f[i].idx == idx ) return f[i];
   assert( false );
   return f[0];
}
bool isfitleaf( unsigned * x , unsigned nx , unsigned * y , unsigned ny )
{
   if( nx == 0 )return true;
   for( unsigned i = 0 ; i < ny ; ++i )
      if( y[i] == x[0] )
      {
         std::swap( y[0] , y[i] );
         if( isfitleaf( x+1,nx-1,y+1,ny-1))return true;
      }
   return false;
}
bool isfit( const vec<Fit> * f , unsigned * x , unsigned nx , unsigned * y , unsigned ny )
{
   if( nx == 0 ) return true;
   for( unsigned i = 0 ; i < ny ; ++ i)
      if( find( f[ y[i] ] , x[0]  ))
      {
         std::swap( y[0] , y[i] );
         if( isfit( f , x+1 , nx-1 , y+1 , ny-1 ) )
            return true;
      }
   return false;
}
static bool dp_re_treemap( InfoCut & ckt , LutTree & t )
{
   unsigned andFlag = ckt._andFlag;
   vec<Fit> fit[ LutTree::N_NODES ];
   
   // LEAF Fitting 
   for( unsigned i = LutTree::N_NODES-1 ; i >= LutTree::N_PARS ; -- i )
   {
      LutTree::LutLeaf & l = t._leaf[ i-LutTree::N_PARS ];

      for( unsigned a = 0 ; a < ckt.size() ; ++a )
      {
         for( int b = 0 ; b < 4 ; ++ b)
         {
            CutSet & cs = ckt._cut[a][b];
            for( int j = 0 ; j < cs.size ; ++ j )
               if( isleaf( cs[j] , b+1 , andFlag ))
               {
                  unsigned child[4] = {l[0],l[1],l[2],l[3]};
                  unsigned cut[b+1];
                  for( int k = 0 ; k <=b ; ++k ) cut[k] = cs[j][k];
                  for( int k = b+1 ; k<4; ++k ) cut[k] = 0;

                  if( isfitleaf( cut,b+1 ,child,4) )
                  {
                     Fit f(a);
                     for( int k = 0 ; k < 4 ; ++ k ) f.cut[ k ] = l[k];
                     fit[i].push(f);
                  }
               }
         }
      }
   }

   // Internal Fitting 
   for( int i = LutTree::N_PARS-1 ; i >=0 ; -- i )
   {
      for( unsigned a = 0 ; a < ckt.size() ; ++ a )
      {
         if( find( fit[i] , a ) ) continue;

         for( int b = 0 ; b < 4 ; ++ b )
         {
            CutSet & cs = ckt._cut[a][b];
            for( int j = 0 ; j < cs.size ; ++ j )
            {
               Cut c = cs[j];
               unsigned child[4] = {i*4+1,i*4+2,i*4+3,i*4+4};
               unsigned cut[b+1];
               for( int k = 0 ; k <=b ; ++k ) cut[k] = c[k];
               for( int k = b+1 ; k<4; ++k ) cut[k] = 0;

               if( isfit( fit , cut , b+1 , child ,4  ) )
               {
                  Fit f(a);
                  for( int k = 0 ; k < 4 ; ++ k ) f.cut[ (child[k]+3)%4 ] = cut[k];
                  fit[i].push(f);
               }
            }
         }
      }
   }

   // Recevering
   if( find( fit[0] , var( ckt._po[0] ) ) == false )return false;

   unsigned short * fun = new unsigned short [ ckt.size() ];
   fun[0] = 0xFFFF;

   unsigned selection[ LutTree::N_NODES ] = {};
   //selection[0] = var( ckt._po[0] );
   for( unsigned i = 0 ; i < LutTree::N_NODES ; ++ i )
      if( find( fit[i] , var( ckt._po[0] ) ) ) 
         t._head = i;
   selection[t._head] = var( ckt._po[0] );
   for( unsigned i = 0 ; i < LutTree::N_NODES ; ++i )
   {
      if( selection[i] == 0 ) continue;
      Fit & f = findfit( fit[ i ] , selection[ i ] );
      t[i] = sim( ckt , fun , selection[i] , f.cut , 4 );
      if( i < LutTree::N_PARS )
         for( int j = 0 ; j < 4 ; ++j )
            selection[ 4*i+j+1 ] = f.cut[j];
   }
   if( sign(ckt._po[0] ) )t[t._head] = ~t[t._head];

   delete [] fun;
   return true;
}
///////////////////////////////////////////////////////////////////////////////
//                       MAIN FUNCTION                                       //
///////////////////////////////////////////////////////////////////////////////
static void synit_setup( InfoCut & ckt )
{
   ckt.init();
   ckt.create_base();
   for( unsigned i = ckt._andFlag ; i < ckt.size() ; ++ i )ckt.update(i);
}
static void read_ckt( const string & file , InfoCut & ckt , CktName * n = NULL )
{
   ckt.read_aig( file.c_str() , n ) ;
   synit_setup( ckt );
}
static void synthesis( InfoCut & in , InfoCut & ckt )
{
   CktInfo::LEVEL_CONSIDER = rand()%2;
   
   in._cut.clear();
   synit( in , ckt );
   synit_setup( ckt );
}
static bool cec( const char * ckt1 , const char * ckt2 )
{
   return false;
}
int main( int argc , const char ** argv )
{
   ArgAnalyzer arg( "map <infile:aig> <outfile:bench> <iofile:leaf> [-remap] [-slower]" , argc , argv );

   InfoCut * ckt = new InfoCut();

   CktName name;
   LutTree tree;

   bool result=false;

   read_ckt( arg[0] , * ckt , & name ); 
   if( ckt->_andFlag < 5 ) cout << cmder << " not handle input < 4 " <<endl;
   if( ckt->_po.sz   > 1 ) cout << cmder << " not handle output > 1 " <<endl;

   if( arg["-remap"].setted )
      tree.read_leaf( arg[2].c_str() );

   unsigned fcnt = 0 ;
   unsigned fcnt2 =0;
   do{
      fcnt = 0;
      do
      {
         InfoCut * nckt = new InfoCut();
         synthesis( * ckt , * nckt );
         delete ckt; 
         ckt = nckt;
         MinCut m[ckt->size()];
         DPmapping( *ckt , m );
         if( m[ckt->size()-1].cost <= 6 ) break;
         else fcnt +=1 ;
      }while( fcnt < 5 );
      if( fcnt == 5 )break;

      if( arg["-remap"].setted == false )
         result = treemap( * ckt , tree );
      else
         result = dp_re_treemap( * ckt , tree );
      fcnt2+=1;
   }while( ! result && fcnt2 < 20);
   
   delete ckt;
   if( result == false ) 
   {
      cout << "I'm SORRY, the function is too complex to map "<< endl;
      cout << cmder << " the mapping is fail "<<endl;
   }
   else
   {
      cout << cmder <<" mapping sucessful "<<endl;
      tree.write_bench( arg[1].c_str() , name );

      if( arg["-remap"].setted == false )tree.write_leaf( arg[2].c_str() );
   }
}
///////////////////////////////////////////////////////////////////////////////
//                       MEMBER FUNCTIONS                                    //
///////////////////////////////////////////////////////////////////////////////
void LutCkt::write_bench( const char * file )
{
   FILE * f = fopen( file , "w" );
    
   for( unsigned i = 1 ; i < pi ; ++ i ) 
      fprintf( f , "INPUT(%s)\n" , names[i].c_str() );
   fprintf( f , "OUTPUT(%s)\n" , names[size-1].c_str() );
   
   for( unsigned i = pi ; i < size ; ++i )
   {
      fprintf( f , "%s = LUT 0x%X (" , names[i].c_str()  ,  luts[i].fun  );
      
      fprintf( f , "%s" , names[luts[i].in[ 0 ]].c_str() );
      for( int j = 1 ; j < luts[i].sz  ; ++ j )
         fprintf( f , " , %s " , names[luts[i].in[j]].c_str() );
      fprintf( f , ")\n" );
   }
   fclose( f );
}
void LutTree::write_bench( const char * file , CktName & n )
{
   FILE * f = fopen( file , "w" );
   for( unsigned i = 0 ; i < n.piName.size() ; ++i )
      fprintf( f , "INPUT(%s)\n" , n.piName[i].c_str() );
   fprintf(  f , "OUTPUT(%s)\n", n.poName[0].c_str() );

   vector<string> name( n.piName.size() +1 );
   name[0] = "VDD"; for( unsigned i = 0 ; i < n.piName.size() ; ++i ) name[i+1] = n.piName[i];

   //fprintf( f , "%s = LUT 0x%X ( n%d , n%d , n%d , n%d )\n" , n.poName[0].c_str() , _dat[0] , 1, 2 , 3, 4 );

   fprintf( f , "%s = BUF( n%d )\n" , n.poName[0].c_str() , _head );
   for( unsigned i = 0 ; i < LutTree::N_PARS ; ++i )
      fprintf( f , "n%d = LUT 0x%X ( n%d , n%d , n%d , n%d )\n" , i , _dat[i] , i*4+1, i*4+2 , i*4+3, i*4+4 );
   for( unsigned i = LutTree::N_PARS ; i < N_NODES ; ++i )
   {
      LutLeaf & x = _leaf[ i - LutTree::N_PARS ];
      fprintf( f , "n%d = LUT 0x%X ( %s , %s , %s , %s )\n" , i , _dat[i] , 
            name[x.in[0]].c_str() , name[x.in[1]].c_str() , name[x.in[2]].c_str(), name[x.in[3]].c_str() );
   }

   fclose(f);
}
void LutCkt::assignName( const CktName * n )
{
   names[0] = "VDD" ;
   if( n )
   {
      for( unsigned i = 0 ; i < n->piName.size() ; ++ i )
         names[ i+1 ] = n->piName[i];
      names[ size-1 ] = n->poName[0];
   }
   for( unsigned i = 1 ; i < size ; ++ i )
      if( names[i].size() == 0 ) names[i] = string("n") + tostr( i );
}
void LutTree::assign_leaf()
{
   Bucket bucket[N_LEAFS];
   bool   hash[ _piidx+1 ];
   memset( hash , 0 , sizeof( bool ) * (_piidx+1) );

   for( unsigned i = 0 ; i < N_LEAFS ; ++ i ) 
      bucket[i].addSeq( 1 , _piidx );

   for( unsigned i = 0 ; i < N_LEAFS ; ++ i ) 
   {
      for( unsigned k = 0 ; k < 4 ; ++ k ) 
      {
         if( _leaf[i].in[k] == 0 )continue;
         unsigned x = _leaf[i].in[k];

         for( unsigned j = 0 ; j < N_LEAFS ; ++ j ) 
         {  
            assert( x < _piidx );
            bucket[j].push( x , dup_num[ diff(i^j) ] );
         }
      }
   }

   for( unsigned i = 0 ; i < N_LEAFS ; ++ i )
   {
      unsigned j = 0 ;
      while( j != 4 )
      {
         if( _leaf[i].in[j] != 0 )
         {
            hash[ _leaf[i].in[j] ] = true ;
            j+=1; 
         }else
         {
            unsigned n = bucket[i].select();
            if( hash[n] == false)
            {
               hash[n] = true; 
               _leaf[i].in[j] = n;
               j+=1; 
            }
         }
      }
      for( j = 0 ; j < 4 ; ++ j ) 
         hash[ _leaf[i].in[j] ] = false;
   }
}
void LutTree::read_leaf( const char * file )
{
   unsigned lim,n; 
   char buf[32];
   FILE * f;

   f = fopen( file , "r" );
   if( f ==NULL){ cout<<"ERROR open "<<endl;exit(1);}
   fscanf( f , "%s%d%d" , buf , & lim , & n );
   assert( strcmp( buf , "treemap" ) == 0 && lim == HEIGHT );

   _piidx = n ;
   for( unsigned i = 0 ; i < N_LEAFS ; ++i ) 
      fscanf( f , "%u%u%u%u" , _leaf[i].in , _leaf[i].in + 1 , _leaf[i].in + 2  , _leaf[i].in + 3  );

   fclose(f);
}
void LutTree::write_leaf( const char * file )
{
   FILE * f = fopen ( file , "w" );
   if(f==NULL){ cout<<"ERROR open "<<endl;exit(1);}

   fprintf( f , "treemap %d %d\n" , HEIGHT , _piidx );
   for( unsigned i = 0 ; i < N_LEAFS ; ++ i ) 
      fprintf( f , "%d %d %d %d\n" , _leaf[i].in[0] , _leaf[i].in[1] , _leaf[i].in[2] , _leaf[i].in[3] );

   fclose( f );
}
///////////////////////////////////////////////////////////////////////////////
//                      BACKUP ALGORITHM                                     //
///////////////////////////////////////////////////////////////////////////////
//___ Cutmap __________________________________________________________________
//  
//  find a map that suitable the cut 
//
//=============================================================================
static bool cutmap( InfoCut & info , LutTree & t , const unsigned * x , unsigned nx , unsigned * y , unsigned ny )
{
   if( nx == 0 ) return true;
   for( unsigned i = 0 ; i < ny ; ++ i )
      if( remap( info , t  , x[0] , y[i] ) )
      {
         std::swap( y[0] , y[i] );
         if( cutmap( info , t , x+1 , nx-1 , y+1 , ny -1 ) )
            return true;
      }
   return false;
}
//___ Cutmap __________________________________________________________________
//  
//  find a map that suitable the cut 
//
//=============================================================================
static bool remap( InfoCut & info , LutTree & t , unsigned x , unsigned y )
{
   static unsigned in[4];
   if( y >= LutTree::N_PARS )
   {
      LutTree::LutLeaf & leaf = t._leaf[ y-LutTree::N_PARS ];
      unsigned bound[4]={};
      for( int i = 3 ; i >= 0 ; --i ) 
      {
         CutSet & c = info._cut[x][i];

         for( int j = 0 ; j < c.size ; ++ j ) 
         {
            if( c.size > 1 )return false; 
            for( int k = 0 ; k <= i ; ++ k ) 
            {
               unsigned n = c[0][k];
               unsigned inside_leaf = false ;
               for( int l = 0 ; l < 4 ; ++ l )
                  if( n == leaf.in[l] )
                  {
                     inside_leaf=true;
                     bound[l] = n;
                     break;
                  }
               if( inside_leaf == false )return false;
            }
            t[y] = sim( info , tmpfun , x , bound , 4 ); 
            return true;
         }
      }
      assert( false );
   }

   unsigned child[4] = {y*4+1,y*4+2,y*4+3,y*4+4};
   for( int i = 3 ; i >=0 ; --i )
   {
      CutSet & c = info._cut[x][i];
      for( int j = 0 ; j < c.size ; ++ j )
      {
         // looking that does the input for cut could fit the mapping 
         unsigned cut[i+1];
         for( int k = 0 ; k <=i ; ++ k )cut[k]=c[j][k];
         for( int k = i+1 ; k < 4 ; ++k )cut[k]=0;
         if( cutmap( info , t , cut , i+1 , child , 4 ) )
         {
            for( int k = 0 ; k < 4 ; ++ k ) in[ (child[k]+3)%4 ] = cut[k];
            t[y] = sim( info , tmpfun , x , in , 4 );
            return true;
         }
      }
   }
   return false;
}
